Transactional memory systems allow a thread to demark a series of memory accesses as a transaction. Threads may execute transactions concurrently. Even though transactions run concurrently, the use of a transactional memory system ensures that the transactions are serializable, meaning that they appear to have executed one after the other.
Transactional memory systems are typically used in computer systems implementing multi-threaded processes. The multiple threads typically share at least some memory in order that the threads may work together and co-ordinate themselves to complete a task. A transactional memory system enables such multiple threads to share some memory in such a way that each thread may complete its transaction without unwanted interference from another thread.
For example, two different threads of a multi-threaded process may read and update the same memory location accessible by the process. Care is then required to ensure that one thread does not modify a value of the shared memory location while the other thread is in the middle of a sequence of operations that depend on the value.
Consider the following bank account example. A first bank account contains £5 and this amount is stored at a memory address A1. A second bank account contains £100 and this amount is stored at another memory address A2. A first transaction or thread is required to transfer £50 from A2 to A1. A second transaction or thread is required to calculate the total amount in the combined bank accounts. Suppose the first thread begins by adding £50 to A1 and this updates the amount stored at A1 to £55. The first thread then proceeds to take away £50 from A2 updating A2 to £50. But, if the second thread executes between these two operations then the second thread may compute an incorrect balance of £155 for both bank accounts rather than the correct total of £105.
Transactional memories may be implemented in software or hardware or hybrids of software and hardware. They provide a means whereby a thread can safely perform a series of shared memory accesses, allowing the thread to complete its transaction, without unwanted interference from another thread. Use of transactional memory systems to manage concurrent threads or processes is often referred to as concurrency control. Typically, programming languages for use with transactional memory systems enable programmers to specify atomic blocks such that there is concurrency control within atomic blocks. In the bank account example given above, a programmer might specify that the first thread's transfer should be atomic so that money is not missed in-transit, and that the second thread's summation is atomic so that it may compute the correct cumulative total for both accounts.
Many existing implementations of atomic blocks in programming languages used with transactional memory systems provide weak atomicity. That is, there is no concurrency control between operations done inside atomic blocks and operations done outside atomic blocks. Operations done inside an atomic block are thought of as making transacted accesses to shared memory locations whereas operations done outside an atomic block are referred to as making non-transacted accesses to memory locations which may or may not be shared.
Existing implementations which use weak atomicity suffer from concurrency control problems. For example, consider the following two threads. Thread 1 comprises an atomic block and a non-transactional update to the variable x. Thread 2 comprises another atomic block.
//Initially x==0, x_shared = true// Thread 1//Thread 2atomic {atomic { x_shared = false; if (x_shared) {} x++;x=100} }
A programmer might reason that Thread 1's update to x_shared allows its subsequent update to x to be made as a normal non-transactional store. After these fragments have run, a programmer might expect that x==100 whichever order the atomic blocks ran in. However, implementations over transactional memory can lead to other results, e.g. x==1 if the implementation of Thread 2's atomic block was still writing back a buffered update to x concurrently with Thread 1's non-transactional store.
To address these problems transactional memories which provide for implementation of atomic blocks that guarantee strong atomicity may be used. Where strong atomicity is guaranteed there is concurrency control between transacted and non-transacted accesses to shared memory. Existing software transactional memory implementations of strong atomicity work by modifying code outside atomic blocks to detect conflicts with concurrent transactions. These accesses are expanded to optimized forms of short transaction. These perform substantially slower than direct accesses, and so performance is typically poor.
Some implementations of software transactional memory with strong atomicity use whole-program analyses to reduce the number of memory accesses that must be expanded in this way. However, the static analysis may require the complete program source code to be available, and it may be time consuming or resource intensive to perform the analysis. Furthermore, the static analysis is typically conservative in the sense that some memory accesses will still be expanded even though they do not experience conflicts during a particular programme execution.
The embodiments described below are not limited to implementations which solve any or all of the problems mentioned above.